public class test04 {
    class Solution {
        List<String> res;
        public List<String> restoreIpAddresses(String s) {
            res = new ArrayList<>();
            backTracking(s,0,0);
            return res;
        }
        private void backTracking(String s,int start,int point){
            if(point==3){
                if(isValid(s,start,s.length()-1)){
                    res.add(s);
                }
                return;
            }
            for(int i = start;i<s.length();i++){
                if(isValid(s,start,i)){
                    point++;
                    s = s.substring(0,i+1)+"."+s.substring(i+1);
                    backTracking(s,i+2,point);
                    point--;
                    s = s.substring(0,i+1)+s.substring(i+2);
                }else{
                    break;
                }
            }
        }
        private boolean isValid(String s,int begin,int end){
            //注意！左闭右闭
            if(begin>end){
                return false;
            }
            if(s.charAt(begin)=='0' && begin!=end){
                return false;
            }
            int num = 0;
            for(int i = begin;i<=end;i++){
                if(s.charAt(i)>'9' || s.charAt(i)<'0'){
                    return false;
                }

                num = num*10 + (s.charAt(i)-'0');
                if(num>255){
                    return false;
                }
            }
            return true;
        }
    }
}
